package org.xingole.leetcode.dp.grid;

import java.util.Arrays;

/*
 * Problem:
 * 
 * You are given a 'rows x cols' matrix 'grid' representing a field of cherries 
 * where 'grid[i][j]' represents the number of cherries that you can collect from
 * the '(i, j)' cell.
 * 
 * You have two roboots that can collect cherries for you :
 * 
 * - Robot #1 is located at the top-left corner '(0, 0)' and 
 * - Robot #2 is located at the top-right corner '(0, cols - 1)'.
 * 
 * Return the maximum number of cherries collection using both robots by following 
 * the rules below:
 * 
 * - From a cell '(i, j)', robots can move to cell '(i+1, j-1)', '(i+1, j)', or '(i+1, j+1)'.
 * - When any robots passes through a cell, it pick up all cherries, and the cell becomes an 
 * empty cell.
 * - When both robots stay in the same cell, only one takes the cherries.
 * - Both robots cannot move outside of the grid at any moment.
 * - Both robots should reach the bottom row in 'grid'.
 * 
 */

public class CherryPickupII {

     public int cherryPickup(int[][] grid) {
          int rows = grid.length;
          int cols = grid[0].length;

          memo = new int[rows][cols][cols];

          // Initial the memo: -1 unknown
          for ( int[][] table : memo ) {
               for ( int[] record : table ) {
                    Arrays.fill(record, -1);
               }
          }

          return cherryPickup(grid, 0, 0, cols - 1, memo);

     }

     /*
      * Approach : Dynamic Programming (Bottom to Up)
      * 
      * Assuming that the grid is a 'm x n' matrix.
      * 
      * Use dynamic programming, define dp[i][j][k]: The maximum cherries that both
      * robots can take when the robot #1 arrive (i, j) from (0, 0) and robot2 #2  
      * arrive (i, k) from (0, n - 1),
      * 
      * When performing state transitions, we enumerate the positions of the two robots
      * in (i-1)th, dj and dk which satify:
      *   - 0 <= dj < n and dj - j in [-1, 0, 1]
      *   - 0 <= dk < n and dk - k in [-1, 0, 1]
      *
      * That means we only enumerate dj in the range of [j - 1, j , j + 1] and determine
      * whether it is in the range of [0, n). The same is true for dk.
      *
      * There our state transfer formula is :
      *
      *    dp[i][j][k] = max ( dp[i-1][dj][dk] + value(i, j , k) )
      * where value(i, j , k) represents the total cherries that both robots can take at 
      * their current locaiton.
      *                     => grid[i][j] + grid[i][k],  if j != k
      *    value(i, j , k) |
      *                     => grid[i][j],                if j = k
      *
      * The base case is : dp[i][0][n-1] = grid[0][0] + grid[0][n-1].
      * 
      */

     public int cherryPickupWithDP(int[][] grid) {
          int m = grid.length;
          int n = grid[0].length;

          // We should use the space optimization technique.

          int[][] f = new int[n][n];  
          int[][] g = new int[n][n];  

          for ( int i = 0; i < n; i++ ) {
               Arrays.fill(f[i], -1);
               Arrays.fill(g[i], -1);
          }

          // The Loop invariant: before each iteration, f[j][k] = dp[i-1][j][k]
          f[0][n-1] = grid[0][0] + grid[0][n-1];
          for ( int i = 1; i < m; i++ ) {
               for ( int j = 0; j < n; j++ ) {
                    for ( int k = 0; k < n; k++ ) {
                         int best = -1;
                         for ( int dj = j - 1; dj <= j + 1; ++dj ) {
                              for ( int dk = k - 1; dk <= k + 1; ++dk ) {
                                   if ( dk >= 0 && dk < n && dj >= 0 && dj < n &&
                                        f[dj][dk] != -1 
                                   ) {
                                        best = Math.max(
                                             best, 
                                             f[dj][dk] + (j == k ? grid[i][j] : grid[i][j] + grid[i][k])
                                        );
                                   }
                              }
                         }
                         // g[j][k] = dp[i][j][k]: g is used to cache the result for next iteration.
                         g[j][k] = best;
                    }
               }

               // update f
               int[][] temp = f;
               f = g;
               g = temp;
          }

          // collect the dp information to get the ultimate answer
          int ans = 0;
          for ( int j = 0; j < n; ++j ) {
               for ( int k = 0; k < n; ++k ) {
                    ans = Math.max(ans, f[j][k]);
               }
          }

          return ans;
     }

     /**
      * The delta of column at each step.
      */
     private int[] delta = {-1, 0, 1};
     private int[][][] memo;

     /**
      * 
      * @return The maximum number of cherries collection using both 
      * robots located (row, col1) and (row, col2), repspectively.
      * @implNote: The time complexity: O(9^n)
      */
     private int cherryPickup(
          int[][] grid, 
          int row, 
          int col1, int col2,
          int[][][] memo
     ) {
          // Use the cache to quickly get the answer.
          if ( memo[row][col1][col2] != -1 ) return memo[row][col1][col2];

          // 2 <= rows , cols <= 70
          int rows = grid.length, cols = grid[0].length;

          int cherries = 0;

          // Collects the current locations cherry.
          if ( col1 == col2 ) cherries += grid[row][col1];
          else                cherries += grid[row][col1] + grid[row][col2];

          if ( row != rows - 1 ) {
               // ... and then collects the rest cherries using recursive solution.
               int restMax = 0;
               int r = row + 1;
               for ( int i = 0; i < 3; i++ ) {
                    int c1 = col1 + delta[i];
                    for ( int j = 0; j < 3; j++ ) {
                         int c2 = col2 + delta[j];

                         // Determine whether robot1 and robot2 can move to the next location.
                         if ( !(c1 < 0 || c1 >= cols) &&
                              !(c2 < 0 || c2 >= cols )
                         ) {
                              restMax = Math.max(
                                   restMax, 
                                   cherryPickup(grid, r, c1, c2, memo)
                              );    
                         }

                    }
               }

               cherries += restMax;
          }

          memo[row][col1][col2] = cherries;
          
          return cherries;
     }

     public static void main(String[] args) {
          CherryPickupII cp2 = new CherryPickupII();

          int[][] grid = null;

          // Example 1:
          grid = new int[][]{{3, 1, 1}, {2, 5, 1}, {1, 5, 5}, {2, 1, 1}};
          System.out.println("Example 1 Output: " + cp2.cherryPickup(grid) );
          System.out.println("Example 1 Excepted: 24");

     }

}
